Tute (Week 2)

1. This is just \(\left\{\frac 11, \frac 12, \frac 13, \frac 14\right\}\), so the cardinality is 4.
2. This is just \(\{0,0,2,6,12\}\), so the cardinality is 4.
3. This is just \(\left\{\frac 14, \frac 1{16}, \frac 1{36}, \frac 1{64}, \frac 1{100}\right\}\) so the cardinality is 5.
4. This is just \(\{3,1,3,1,\ldots\}\) so the cardinality is 2.

1. \(|A \cup B| = |A| + |B| - |A \cap B| = m+n-k\)
2. \(|A \setminus B| = |A| - |A \cap B| = m-k\)
3. \(|A \oplus B| = |A \cup B| - |A \cap B| = m+n-2k\)

The general approach here is to tally up the words of each possible length separately.

1. \(A\) has \(3^0 + 3^1 + 3^2 + 3^3 = 1+3+9+27=40\) elements.
2. \(B\) has \(4+8+16 = 28\) elements

3. Since B has no words of length 0 and 1, we only need to tally up the words from A. For lengths 2 and 3 we have that the B-words are a subset of the A-words, so to get the words that only occur in A we subtract the number of A-words from the number of B-words. Finally, since A has no words of length 4, we only need to count the B-words. Thus:

   \begin{array}{rlr} & card(A \oplus B) & = \\ & 1 + 3 + (9 - 4) + (27 - 8) + 16 & = \\ & 44& \end{array}

4. It is certainly fewer than \(40\times 28=1120\) because \(wv = w'v'\) when, e.g. \(w = \lambda\), \(v=aaa\), \(w'=a\), \(v'=aa\). We need to count all the words over \(\{a,b,c\}\), with length between \(2\) and \(7\), where \(c\)'s can only occur up to the position \(\min\{3,\mathsf{length}(w)-2\}\)

   1. Length \(2\) (no \(c\)'s): \(2 \times 2 = 4\) words
   2. Length \(3\) (\(c\) only possible in first position): \(3 \times 2 \times 2 = 12\)
   3. Length \(4\) (\(c\) only possible in first two positions): \(3 \times 3 \times 2 \times 2 = 36\)
   4. Length \(5\) (\(c\) only possible in first three positions): \(3^3 \times 2^2 = 108\)
   5. Length \(6\) (\(c\) only possible in first three positions): \(3^3 \times 2^3 = 216\)
   6. Length \(7\) (\(c\) only possible in first three positions): \(3^3 \times 2^4 = 432\)

   Total: 808.

As can be checked with a Venn diagram: \[A\setminus(B\setminus C)=((A \setminus B) \setminus C) \cup (A \cap C)\] so when \(A \cap C = \emptyset\) we have equality.

Note: using the Principle of Duality, we only need to show one equality for each part.

Annihilation (Part 1):

\begin{array}{rlr} A \cap \emptyset &= A \cap (A \cap A^c)&\quad\text{(Complementation)}\\ &= (A \cap A) \cap A^c&\quad\text{(Associativity)}\\ &= A \cap A^c&\quad\text{(Idempotence)}\\ &= \emptyset & \text{(Complementation)} \end{array}

Double Complementation (Part 2):

Following the hint, if \(A \cap B = \emptyset\) and \(A \cup B = \mathcal{U}\):

\begin{array}{rlr} A^c &= A^c \cap \mathcal{U} &\quad\text{(Identity)}\\ &= A^c \cap (A \cup B) &\quad\text{(Assumption)}\\ &= (A^c \cap A) \cup (A^c \cap B)&\quad\text{(Distributivity)}\\ &= (A \cap A^c) \cup (A^c \cap B)&\quad\text{(Commutativity)*}\\ &= \emptyset \cup (A^c \cap B)&\quad\text{(Complementation)}\\ &= (A^c \cap B) \cup \emptyset&\quad\text{(Commutativity)*}\\ &= A^c \cap B&\quad\text{(Identity)}\\ &= B \cap A^c & \quad\text{(Commutativity)}\\ &= (B \cap A^c) \cup \emptyset&\quad\text{(Identity)}\\ &= (B \cap A^c) \cup (B \cap A)&\quad\text{(Assumption)}\\ &= B \cap (A^c \cup A)&\quad\text{(Distributivity)}\\ &= B \cap (A \cup A^c)&\quad\text{(Commutativity)*}\\ &= B \cap \mathcal{U}&\quad\text{(Complementation)}\\ &= B&\quad\text{(Identity)} \end{array}

Now we have, using Commutativity and Complementation:

\begin{array}{l} A^c \cap A = A \cap A^c = \emptyset\\ A^c \cup A = A \cup A^c = \mathcal{U} \end{array}

So \(A = (A^c)^c\).

De Morgan's Laws (Part 3):

We have:

\begin{array}{rlr} (A \cap B) \cap (A^c \cup B^c) &= A \cap (B \cap (A^c \cup B^c))&\quad\text{(Associativity)}\\ &=A \cap ((B \cap A^c) \cup (B \cap B^c))&\quad\text{(Distributivity)}\\ &=A \cap ((B \cap A^c) \cup \emptyset) & \quad\text{(Complementation)}\\ &=A \cap (B\cap A^c) &\quad\text{(Identity)}\\ &=(A \cap B) \cap A^c &\quad\text{(Associativity)}\\ &=(B \cap A) \cap A^c &\quad\text{(Complementation)}\\ &=B \cap (A \cap A^c) &\quad\text{(Associativity)}\\ &=B \cap \emptyset &\quad\text{(Complementation)}\\ &=\emptyset &\text{(Annihilation: see (a))} \end{array}

By the Principle of Duality we also have \[(X \cup Y) \cup (X^c \cap Y^c) = \mathcal{U}\]

So,

\begin{array}{rlr} (A \cap B) \cup (A^c \cup B^c)&= (A^c \cup B^c) \cup (A \cap B) &\quad\text{(Commutativity)}\\ &= (A^c \cup B^c) \cup ((A^c)^c \cap (B^c)^c) &\:\text{(Double complement)}\\ &= \mathcal{U}&\:\quad\text{(from above)} \end{array}

It follows from the previous part (Uniqueness of complement) that \((A \cap B)^c = (A^c \cup B^c)\).

\begin{array}{rlr} &\;\;\; (A \cap B^c) \cup (B \cap A^c) \\ &= ((A \cap B^c) \cup B) \cap ((A\cap B^c) \cup A^c)&\text{(Distributivity)}\\ &= (B \cup (A \cap B^c)) \cap (A^c \cup (A \cap B^c))&\text{(Commutativity)}\\ &= ((B \cup A) \cap (B \cup B^c)) \cap ((A^c \cup A) \cap (A^c \cup B^c))&\text{(Distributivity)}\\ &= ((B \cup A) \cap (B \cup B^c)) \cap ((A^c \cup (A^c)^c) \cap (A^c \cup B^c))&\text{(Dbl. compl.)}\\ &= ((B \cup A) \cap \mathcal{U}) \cap (\mathcal{U} \cap (A^c \cup B^c))&\text{(Complement)}\\ &= ((A \cup B) \cap \mathcal{U}) \cap ((A^c \cup B^c) \cap \mathcal{U})&\text{(Commutativity)}\\ &= (A \cup B) \cap (A^c \cup B^c)&\text{(Identity)}\\ &= (A \cup B) \cap (A \cap B)^c&\text{(De Morgan's law)} \end{array}

To show that \(R\) is a partial order, we need to show that it is reflexive, antisymmetric, and transitive.

1. Reflexive: For all \(w \in \Sigma^*\) we observe that \(w = w \lambda\). Hence, \((w,w) \in R\), and so \(R\) is reflexive.
2. Antisymmetric: Suppose \((w,v) \in R\) and \((v,w) \in R\). Then there exists \(x,y \in \Sigma^*\) such that \(v = wx\) and \(w=vy\). So \(w=wxy\), and so \(\mathsf{length}(xy)=0\) and \(xy=\lambda\). Therefore \(x=y=\lambda\) so \(w=v\lambda = v\). So \(R\) is antisymmetric.
3. Transitive: Suppose \((w,v), (v,x) \in R\). Then there exists \(y,z\) such that \(wy=v\) and \(vz=x\). But then \(w(yz) = (wy)z = vz = x\) so \((w,x) \in R\). Hence \(R\) is transitive.